package lcr;

public class Test0066 {
    public static void main(String[] args) {
        MapSum mapSum = new MapSum();
        mapSum.insert("apple",3);
        mapSum.insert("apple",2);
        System.out.println(mapSum.sum("apple"));
    }
}

class MapSum {
    Trie trie=new Trie();
    /** Initialize your data structure here. */
    public MapSum() {

    }

    public void insert(String key, int val) {
        trie.insert(key.toCharArray(),0,val);
    }

    public int sum(String prefix) {
        char[] chars = prefix.toCharArray();
        Trie current = trie;
        for (char c : chars) {
            if (current.get(c)==null) return 0;
            else current=current.get(c);
        }
        return current.sum;
    }

    class Trie{
        Trie[] children;
        int sum;
        int val;
        public Trie(){
            sum = 0;
            val = 0;
        }

        public int insert(char[] chars,int index,int value){
            if (index == chars.length) {
                int change = value - val;
                val = value;
                sum += change;
                return change;
            }
            if (children == null) children = new Trie[26];

            Trie trie = children[chars[index] - 'a'];
            if (trie == null) {
                trie = new Trie();
                children[chars[index] - 'a'] = trie;
            }

            int change = trie.insert(chars, index + 1, value);
            sum += change;
            return change;
        }

        public Trie get(char c){
            if (children==null) return null;
            return children[c-'a'];
        }
    }
}
